/**
 * @file   DoubleLinkedList.h
 * @author ywl <ywl@ywl-VirtualBox>
 * @date   Thu Oct  6 21:47:55 2022
 * 
 * @brief  Implementation of doubly linked list
 * 
 * 
 */

#include <algorithm>
#include <iostream>

template <typename DT>
class DoubleLinkedList
{
private:
    struct Node
    {
	DT data;
	Node *prev;
	Node *next;

	Node(const DT & d = DT{}, Node *p = nullptr, Node *n = nullptr)
	    : data{d}, prev{p}, next{n} {}
	
	Node(DT && d, Node *p = nullptr, Node *n = nullptr)
	    : data{std::move(d)}, prev{p}, next{n} {}
    };
    
public:
    class const_iterator
    {
    public:
        const_iterator(): current{nullptr}
	{}

	const DT & operator* () const
	{
	    return retrieve();
	}

	const_iterator & operator++ ()
	{
	    current = current->next;
	    return *this;
	}

	const_iterator operator++ (int)
	{
	    const_iterator old = *this;
	    ++(*this);
	    return old;
	}

	bool operator== (const const_iterator & rhs) const
	{
	    return current == rhs.current;
	}
	bool operator!= (const const_iterator & rhs) const
	{
	    return !(*this == rhs);
	}
	
    protected:
	Node *current;

	DT & retrieve() const
	{
	    return current->data;  
	}
	const_iterator(Node *p) : current{p}
	{}
	
	friend class DoubleLinkedList<DT>;
    };
    
    class iterator : public const_iterator
    {
    public:
	iterator()
	{}
	DT & operator* ()
	{
	    return const_iterator::retrieve();
	}
	const DT & operator* () const
	{
	    return const_iterator::operator*();
	}

	iterator & operator++ ()
	{
	    this->current = this->current->next;
	    return *this;
	}

	iterator & operator++(int)
	{
	    iterator old = *this;
	    ++(*this);
	    return old;
	}

	iterator & operator= (const iterator & rhs)
	{
	    iterator copy = rhs;
	    std::swap(*this,copy);
	    return *this;
	}
    protected:
        iterator(Node *p) : const_iterator{p}
	{}
	
	friend class DoubleLinkedList<DT>;
    };

public:
    DoubleLinkedList()
    {
	init();
    }
    DoubleLinkedList(const DoubleLinkedList & rhs)
    {
	init();
	for(auto & x: rhs)
	    push_back(x);
    }
    ~DoubleLinkedList()
    {
	clear();
	delete head;
	delete tail;
    }
    DoubleLinkedList & operator= (const DoubleLinkedList & rhs)
    {
	DoubleLinkedList copy = rhs;
	std::swap(*this,copy);
	return *this;
    }
    DoubleLinkedList(DoubleLinkedList && rhs)
	: theSize{rhs.theSize},head{rhs.head},tail{rhs.tail}
    {
	rhs.theSize = 0;
	rhs.head = nullptr;
	rhs.tail = nullptr;
    }
    DoubleLinkedList & operator= (DoubleLinkedList && rhs)
    {
	std::swap(theSize, rhs.theSize);
	std::swap(head, rhs.head);
	std::swap(tail,rhs.tail);

	return *this;
    }

    iterator begin()
    {
	return head->next;
    }
    const_iterator begin() const
    {
	return head->next;
    }
    iterator end()
    {
	return tail;
    }
    const_iterator end() const
    {
	return tail;
    }

    int size() const
    {
	return theSize;
    }
    bool empty() const
    {
	return size() == 0;
    }

    void clear()
    {
	while(!empty())
	    pop_front();
    }
    DT & front()
    {
	return *begin();
    }
    const DT & front () const
    {
	return *begin();
    }
    DT & back()
    {
	return *--end();
    }
    const DT & back() const
    {
	return *--end();
    }
    void push_front(const DT & x)
    {
	insert(begin(), x);
    }
    void push_front(DT && x)
    {
	insert(begin(), std::move(x));
    }
    void push_back(const DT & x)
    {
	insert(end(), x);
    }
    void push_back(DT && x)
    {
	insert(end(), std::move(x));
    }
    void pop_front()
    {
	erase(begin());
    }
    void pop_back()
    {
	erase(--end());
    }

    /** 
     * Print the doubly linked list.
     * 
     */
    void printList() const
    {
	if(empty())
	    std::cout << "This is an empty list!" << std::endl;
	else
	{
	    const_iterator itr = begin();
	    // print the first item
	    std::cout << "[ " << *itr++;
	    
	    while(itr != end())
		std::cout << ", " << *itr++;
	    std::cout << " ]" << std::endl;
	}
    }

    /** 
     * find the position of _val in _list.
     * 
     * @param _list 
     * @param _val 
     * 
     * @return 
     */
    iterator find(DoubleLinkedList<DT>& _list, const DT & _val)
    {
	for(iterator itr = _list.begin(); itr != _list.end(); ++itr)
	    if(*itr == _val)
		return itr;
	// Nothing found
	return nullptr;
    }
    
    /** 
     * Insert x before itr.
     * 
     * @param itr 
     * @param x 
     * 
     * @return 
     */
    iterator insert(iterator itr, const DT & x)
    {
	Node *p = itr.current;
	theSize++;
	return {p->prev = p->prev->next = new Node{x, p->prev, p}};
    }
    iterator insert(iterator itr, DT && x)
    {
	Node *p = itr.current;
	theSize++;
	return {p->prev = p->prev->next = new Node{std::move(x), p->prev, p}};
    }

    /** 
     * Erase item at itr.
     * 
     * @param itr 
     * 
     * @return 
     */
    iterator erase(iterator itr)
    {
	Node *p = itr.current;
	iterator retVal{p->next};
	p->prev->next = p->next;
	p->next->prev = p->prev;
	delete p;
	theSize--;

	return retVal;
    }
    iterator erase(iterator from, iterator to)
    {
	for(iterator itr = from; itr != to; )
	    itr = erase(itr);

	return to;
    }

private:
    int theSize;
    Node *head;
    Node *tail;

    void init()
    {
	theSize = 0;
	head = new Node;
	tail = new Node;
	head->next = tail;
	tail->prev = head;
    }
};
